/*
 * @Author: w
 * @Date: 2022-02-19 22:38:39
 * @Description: 剑指 Offer 35. 复杂链表的复制
 */

// 如何保证random是新的Node，hashmap+回溯 节点拆分

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */

// hashMap
var copyRandomList = function (head) {
  const map = new Map();
  let ponit = head;
  while (ponit) {
    let newNode = new Node(ponit.val, ponit.next, ponit.random);
    map.set(ponit, newNode);
    ponit = ponit.next;
  }
  ponit = map.get(head);
  while (ponit) {
    ponit.next = map.get(ponit.next) || null;
    ponit.random = map.get(ponit.random) || null;
    ponit = ponit.next;
  }
  return map.get(head);
};

// 方法一：回溯 + 哈希表
var copyRandomList = function (head, cachedNode = new Map()) {
  if (head === null) {
    return null;
  }
  if (!cachedNode.has(head)) {
    cachedNode.set(head, { val: head.val });

    Object.assign(cachedNode.get(head), {
      next: copyRandomList(head.next, cachedNode),
      random: copyRandomList(head.random, cachedNode) // cachedNode.get(head.random)
    });
  }
  return cachedNode.get(head);
};

// 方法二：迭代 + 节点拆分
var copyRandomList = function (head) {
  if (head === null) {
    return null;
  }
  // 拆分，原来的链表 每个node后面插入 newNode
  for (let node = head; node !== null; node = node.next.next) {
    const nodeNew = new Node(node.val, node.next, null);
    node.next = nodeNew;
  }
  // 把random指向新的newNode
  for (let node = head; node !== null; node = node.next.next) {
    const nodeNew = node.next;
    nodeNew.random = node.random !== null ? node.random.next : null;
  }
  // 合并链表，移除旧的node
  const headNew = head.next;
  for (let node = head; node !== null; node = node.next) {
    const nodeNew = node.next;
    node.next = node.next.next;
    nodeNew.next = nodeNew.next !== null ? nodeNew.next.next : null;
  }
  return headNew;
};
